package com.cb2.algorithm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/boundary-of-binary-tree'>二叉树的边界(Boundary of Binary Tree)</a>
 * <p>二叉树的 边界 是由 根节点 、左边界 、按从左到右顺序的 叶节点 和 逆序的右边界 ，按顺序依次连接组成。</p>
 * <p>
 * 左边界 是满足下述定义的节点集合：
 *     <ul>
 *         <li>根节点的左子节点在左边界中。如果根节点不含左子节点，那么左边界就为 空 。</li>
 *         <li>如果一个节点在左边界中，并且该节点有左子节点，那么它的左子节点也在左边界中。</li>
 *         <li>如果一个节点在左边界中，并且该节点 不含 左子节点，那么它的右子节点就在左边界中。</li>
 *         <li>最左侧的叶节点 不在 左边界中。</li>
 *     </ul>
 * </p>
 * <p>右边界 定义方式与 左边界 相同，只是将左替换成右。即，右边界是根节点右子树的右侧部分；叶节点 不是 右边界的组成部分；如果根节点不含右子节点，那么右边界为 空 。</p>
 * <p>叶节点 是没有任何子节点的节点。对于此问题，根节点 不是 叶节点。</p>
 * <p>给你一棵二叉树的根节点 root ，按顺序返回组成二叉树 边界 的这些值。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：root = [1,null,2,3,4]
 *                      1
 *                        \
 *                         2
 *                       /   \
 *                      3     4
 *      输出：[1,3,4,2]
 *      解释：
 *          - 左边界为空，因为二叉树不含左子节点。
 *          - 右边界是 [2] 。从根节点的右子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以右边界只有 2 。
 *          - 叶节点从左到右是 [3,4] 。
 *          按题目要求依序连接得到结果 [1] + [] + [3,4] + [2] = [1,3,4,2] 。
 *
 *  示例 2：
 *      输入：root = [1,2,3,4,5,6,null,null,null,7,8,9,10]
 *                          1
 *                     /        \
 *                    2          3
 *                  /  \        /
 *                4     5      6
 *                     / \   /   \
 *                    7   8 9    10
 *      输出：[1,2,4,7,8,9,10,6,3]
 *      解释：
 *          - 左边界为 [2] 。从根节点的左子节点开始的路径为 2 -> 4 ，但 4 是叶节点，所以左边界只有 2 。
 *          - 右边界是 [3,6] ，逆序为 [6,3] 。从根节点的右子节点开始的路径为 3 -> 6 -> 10 ，但 10 是叶节点。
 *          - 叶节点从左到右是 [4,7,8,9,10]
 *          按题目要求依序连接得到结果 [1] + [2] + [4,7,8,9,10] + [6,3] = [1,2,4,7,8,9,10,6,3] 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 10^4] 内</li>
 *     <li>-1000 <= Node.val <= 1000</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/5/20 10:29
 */
public class LC0545BoundaryOfBinaryTree_M {
    static class Solution {
        public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            // 根节点 + 左边界 + 从左到右的叶节点 + 逆序的右边界
            List<Integer> resList = new ArrayList<>();
            if (root == null) {
                return resList;
            }
            resList.add(root.val);
            leftBoundary(root.left, resList);
            leaves(root.left, resList);
            leaves(root.right, resList);
            rightBoundary(root.right, resList);
            return resList;
        }

        // preorder
        private void leftBoundary(TreeNode currNode, List<Integer> resList) {
            // 空节点或者叶子节点，直接返回
            if (currNode == null || (currNode.left == null && currNode.right == null)) {
                return;
            }
            resList.add(currNode.val);
            if (currNode.left != null) {
                leftBoundary(currNode.left, resList);
            } else {
                leftBoundary(currNode.right, resList);
            }
        }

        private void leaves(TreeNode currNode, List<Integer> resList) {
            if (currNode == null) {
                return;
            }
            if (currNode.left == null && currNode.right == null) {
                resList.add(currNode.val);
                return;
            }
            leaves(currNode.left, resList);
            leaves(currNode.right, resList);
        }

        // postorder
        private void rightBoundary(TreeNode root, List<Integer> resList) {
            if (root == null || (root.left == null && root.right == null)) {
                return;
            }
            if (root.right == null) {
                rightBoundary(root.left, resList);
            } else {
                rightBoundary(root.right, resList);
            }
            resList.add(root.val);
        }
    }
}
